The present invention relates generally to packet switched data handling systems and, more particularly, to a high speed router employing a crossbar type switch and multiple independent forwarding processors.
There is increasing interest in providing communications between disparate computer systems and even between networks of differing characteristics. Further, with the availability of very high bandwidth trunk lines, e.g., using fiber optic cables, there is increasing interest in combining traffic from a great variety of sources for transmission through a single trunk line or link. For wide area networks, packet switching technology is widely used where information to be transmitted is broken into packets of data which are preceded by headers containing information useful in routing. The header may also identify the source and the destination. Whether truly packet switched or not, most digital communication systems employ message formats in which there is an identifying header of some sort.
As is well known, data network usage is expanding at a great rate both in terms of private networks and also public networks such as the Internet. While transmission link bandwidths keep improving, the technology of the systems which interconnect the links has lagged behind. In particular, routers are needed which can keep up with the higher transmission link bandwidths. A high speed router needs to achieve three goals. First, it needs to have enough internal bandwidth to move packets between its input and output interfaces at the desired rates. Second, it needs enough packet processing power at the interfaces to forward the packets and, third, the router needs to be able to redirect the packets between possible paths at the requisite rates. Processing power available for making forwarding decisions is a resource which should be made available fairly and not be subject to hogging or malicious pre-emption.
Most currently available or conventional routers are bus based, that is, a high speed bus is provided which can link a single input to a single output at one time. The router of the present invention utilizes a crossbar switch type interconnection between inputs and outputs. While crossbar-type interconnection schemes have been utilized heretofore in various contexts, one problem which exists in the context of packet switching is the allocation of available paths through the crossbar. As is understood by those skilled in the art, only a limited number of switch points can be utilized at any one time since a single input should not be connected to more than one output at a given time and, likewise, each output should only be connected to a single input. A scheme for quickly and fairly allocating switch points in a cross-bar type of switch is disclosed and claimed in copending and coassigned application Ser. No. 08/656,546 entitled Data Packet Router and filed May 31, 1996 in the name of Philip P. Carvey et al. The disclosure of that application is incorporated herein by reference.
Among the several objects of the present invention may be noted the provision of a novel router architecture which provides flexible and protectable processing power for making forwarding decisions; the provision of such an architecture in which such processing power can be allocated fairly and can be protected from hogging or malicious pre-emption; the provision of such an architecture which allows a single router to be shared among several functionally independent and private networks, i.e. so-called virtual private networks; the provision of such a router architecture that can handle multigigabit data throughputs; the provision of such a router architecture which can accommodate data links of disparate types; the provision of such a router architecture which is highly reliable; the provision of such a router architecture which is easily maintained and which is highly reliable; the provision of such a router architecture which is of relatively simple and inexpensive construction in relation to its capabilities. Other objects and features will be in part apparent and in part pointed out hereinafter.